#include<cstdio>
#include<algorithm>
#include<map>
#include<cassert>

using namespace std;

#define mp make_pair
#define fi first
#define se second

const int inf=1000000000;
const int MAXN=50000,MAXM=100000;

struct node;
node*emp;

struct Info
{
	// 必要信息
	Info()
	{
		// 必要信息构造函数
	}
	Info()
	{
	}
};

struct Mark
{
	// 标记所需信息
	bool rev;
	Mark(bool r=0)
	{
		rev=r;
	}
};

struct node
{
	node*f,*c[2];
	Info self; // 节点自身信息
	Info info; // 节点统领子树信息
	Mark mark; // 标记
	void init();
	bool getSide()
	{
		return f->c[1]==this;
	}
	void setc(bool dir,node*x)
	{
		c[dir]=x;
		x->f=this;
	}
} buf[MAXN+MAXM];

// 初值设定
void node::init()
{
	f=c[0]=c[1]=emp;
	info=self=Info();
	mark=Mark(); // 初始标记
}

bool isRoot(node*x)
{
	return (x->f==emp) || (x->f->c[0]!=x&&x->f->c[1]!=x); 
}

Info operator + (const Info&info,const Mark&mark)
{
	// 将mark作用于info
	return info;
}

Mark operator + (const Mark& Befo,const Mark& Late)
{
	// mark相加
	Mark ret;
	ret.rev=(int)Befo.rev^(int)Late.rev;
	return ret;
}

Info operator + (const Info&a,const Info&b)
{
	// 合并info
	Info ret;
	return ret;
}

node* update(node*x)
{
	x->info=x->c[0]->info+x->self+x->c[1]->info;
	return x;
}

void pushMark(node*x,Mark mark)
{
	if (x==emp) return;
	if (mark.rev) swap(x->c[0],x->c[1]);
	x->info=x->info+mark;
	x->self=x->self+mark;
	x->mark=x->mark+mark;
}

void pushDown(node*x)
{
	pushMark(x->c[0],x->mark);
	pushMark(x->c[1],x->mark);
	x->mark=Mark(); // 修改此处标记
}

void rot(node*x)
{
	node*y=x->f;
	node*z=y->f;
	bool d=x->getSide();
	pushDown(y); pushDown(x);
	x->f=z; if (!isRoot(y)) z->c[y->getSide()]=x;
	y->setc(d,x->c[!d]);
	x->setc(!d,update(y));
}

node* splay(node*x)
{
	for(pushDown(x);!isRoot(x);rot(x))
		if (!isRoot(x->f))
			rot((x == x->f->c[1]) == (x->f == x->f->f->c[1]) ? x->f : x);
	return update(x);
}

// 该操作返回值一定是splay的根
node*access(node*x)
{
	node*y=emp;
	for(;x!=emp;x=x->f)
	{
		x=splay(x);
		x->c[1]=y;
		y=update(x);
	}
	return y;
}

// 该操作后x不一定是splay的根
void toRoot(node*x)
{
	pushMark(access(x),Mark(true));
}

node* tail(node*x)
{
	node*now=access(x);
	while(now->c[0]!=emp)
		now=now->c[0];
	splay(now);
	return now;
}

bool isConnect(node*x,node*y)
{
	return tail(x)==tail(y);
}

void link(node*x,node*y)
{
	toRoot(x);
	splay(x);
	x->f=y;
}

void cut(node*x,node*y)
{
	toRoot(x);
	access(x);
	splay(y);
	y->f=emp;
}

Info ask(node*x,node*y)
{
	toRoot(x);
	return access(y)->info;
}

void run()
{
	// 主程序
}

int main()
{
	freopen("model.in","r",stdin);
	freopen("model.out","w",stdout);
	
	emp=new node();
	// 设置emp各项属性
	run();
	delete emp;
	return 0;
}
